/*
516. [最长回文子序列]
(https://leetcode.cn/problems/longest-palindromic-subsequence/description/)
辛泽豪
*/

code：


// 假设 base 和 mod 已经在其他地方定义了
const long long base = ¾;  // 选择一个合适的基数
const long long mod = 1e9 + 7;  // 选择一个合适的模数

int minCut(string s) {
    int n = s.size();  // 字符串s的长度
    vector<int> dp(n + 1, INT_MAX);  // dp数组，dp[i]表示从0到i-1的子串最少分割次数
    dp[0] = -1;  // 空字符串不需要切割
    
    for (int i = 1; i <= n; i++) {  // 外层循环，i表示当前考虑的子串结束位置
        long long fb = 0, ff = 0;  // fb表示从后往前，ff表示从前往后的字符串哈希值
        long long mul = 1;  // 用于计算从前往后的哈希值
        
        for (int j = i; j >= 1; j--) {  // 内层循环，j表示当前考虑的子串开始位置
            int num = s[j - 1] - 'a';  // 当前字符转换为数字
            
            // 更新从后往前的哈希值
            fb = (fb * base % mod + num) % mod;
            
            // 更新从前往后的哈希值
            ff = (num * mul % mod + ff) % mod;
            mul = mul * base % mod;  // 更新乘法因子
            
            // 如果从j到i的子串是回文
            if (fb == ff) {
                // 更新dp[i]，取当前dp[i]和dp[j-1]+1的最小值
                dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }
        // 打印每一步的dp状态，方便调试
        cout << i << " " << dp[i] << endl;
    }
    
    // 返回从0到n-1的子串最少分割次数
    return dp[n];
}
